package com.cacheserverdeploy.algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.cacheserverdeploy.node.ConsumeNode;
import com.cacheserverdeploy.node.NetworkNode;
import com.cacheserverdeploy.util.Const;
import com.cacheserverdeploy.util.Util;

public class ThirdStepCopy {
	
	List<List<Integer>> severPathsResult = new ArrayList<>();// 消费点到服务器的最短路径

	public int adjust(List<Integer> severlocation, NetworkNode[] nodes, ConsumeNode[] consumeNodes) {
		SingleSourceDijkstra ssDijkstra = new SingleSourceDijkstra();
//		severPaths.clear();

		List<List<Integer>> severPaths = new ArrayList<>();// 消费点到服务器的最短路径		
		
		int[] severs = new int[severlocation.size()];// 终点应该是服务器点
		for (int i = 0; i < severs.length; i++) {
			
			severs[i] = severlocation.get(i);
		}
		
		// 流量服务器位置还原
		for (NetworkNode node : nodes) {
			node.restoreDischarge();
			if (severlocation.contains(node.getId())) {
				node.setLocatedServer(true);
			}else{
				node.setLocatedServer(false);
			}
			
		}

		// System.out.println("---------------------------我是分割线----------------------");
		for (int i = 0; i < consumeNodes.length; i++) {
			int start = consumeNodes[i].getNetworkNodeId();
			if (!nodes[start].isLocatedServer()) {
				// 有可能是服务器本身
				// 该点到其他所有点的最短距离

				// 这儿一定要注意，调用了最短函数之后，会修改本身的邻接矩阵
				int[][] matrix2 = Util.constructMatrix(nodes);
				List<List<Integer>> shortPaths = ssDijkstra.dijkstra_Path(matrix2, start, severs);
				// 该点到其他消费点最短路径，例如[43,44]
				List<Integer> shortestPath = ssDijkstra.findMinPath(shortPaths);
				// System.out.println(shortestPath.toString());
				// 全部存储下来
				severPaths.add(shortestPath);
			}

		}

		//所有的都是服务器
		if (severPaths.size()==0) {
			return Const.SERVER_COST*consumeNodes.length;
		}else {
			setDischarge(severPaths, nodes, consumeNodes, severlocation);// 设置流量

			// 消费点所需要的流量
			List<Integer> requireDischarge = new ArrayList<>();
			for (int i = 0; i < consumeNodes.length; i++) {
				requireDischarge.add(consumeNodes[i].getRequired());
			}

			List<Integer> order = findPosition(requireDischarge);

			for (int i = order.size() - 1; i >= 0; i--) {// 需求量最大的点

				int consumid = order.get(i);
				int fromID=consumeNodes[consumid].getNetworkNodeId();//需要满足的消费点直接相连的点
				List<List<Integer>> subPath = findPathsByFromid(fromID, severPaths);
				if (subPath.size() != 0) {// 表明该点没安放服务器
					// 这条路的应该先不分配，看看最大能分多少
					restoreDischarge(subPath, nodes);

					for (List<Integer> pathNeedtoAdjust : subPath) {// 如果路径有超限

						int consumeNeed = pathNeedtoAdjust.get(pathNeedtoAdjust.size() - 1);

						pathNeedtoAdjust.remove(pathNeedtoAdjust.size() - 1);// 将最后的流量移除
						int maxDischarge = 0;
						// 找到这条路最大能提供的
						maxDischarge = maxExtraDischargePathCanAfford(pathNeedtoAdjust, nodes);// 刚开始能最大的是多少

						if (maxDischarge >= consumeNeed) {
							// 如果能提供的满足要求
							pathNeedtoAdjust.add(consumeNeed);// 如果能满足先满足
							// System.out.println("满足");
							for (int j = 0; j < pathNeedtoAdjust.size() - 2; j++) {// 最后一位为数字
								int require = pathNeedtoAdjust.get(pathNeedtoAdjust.size() - 1);
								nodes[pathNeedtoAdjust.get(j + 1)].setDischargeTo(nodes[pathNeedtoAdjust.get(j)].getId(),
										require);// 应该叠加流量
							}

						} else {

							pathNeedtoAdjust.add(maxDischarge);
							// 这儿有一个问题，需要设置为里面容量较小的值！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
							// severPaths.get(index)中的都要变
							for (int j = 0; j < pathNeedtoAdjust.size() - 2; j++) {// 最后一位为数字
								int require = pathNeedtoAdjust.get(pathNeedtoAdjust.size() - 1);
								nodes[pathNeedtoAdjust.get(j + 1)].setDischargeTo(nodes[pathNeedtoAdjust.get(j)].getId(),
										require);// 设置流量变小
							}

							// 这儿一定要注意，调用了最短函数之后，会修改本身的邻接矩阵
							int[][] matrix = Util.constructMatrix(nodes);
							// 服务器之间不同

							// matrix[toID][fromID] = 100000;// 那么这条路不同，反着找的

							// int[] fromIDs = {
							// pathNeedtoAdjust.get(pathNeedtoAdjust.size()-2)
							// };//最后的终点
							int[] fromIDs = new int[severlocation.size()];// 终点应该是服务器点
							for (int j = 0; j < fromIDs.length; j++) {
								fromIDs[j] = severlocation.get(j);
							}

							// 该点到其他所有点的最短距离，找到该点的起始点到终点的最短距离，但是不能走之前的那条路
							List<List<Integer>> shortPaths = ssDijkstra.dijkstra_Path(matrix, pathNeedtoAdjust.get(0),
									fromIDs);
							// 该点到其他消费点最短路径，例如[43,44]
							// 新的路径
							int newDischargeNeed = consumeNeed - maxDischarge;// 还需要的路径

							int newPathToDispath = 0;// 新的线路要带的
							int dischargeCanaffort = 0;

							do {

								List<Integer> shortestPath = ssDijkstra.findMinPath(shortPaths);
								shortPaths.remove(shortestPath);// 删除现在的

								shortestPath.remove(shortestPath.size() - 1);// 这儿经常报错

								int maxDischrgeForNew = maxExtraDischargePathCanAfford(shortestPath, nodes);
								dischargeCanaffort = maxDischrgeForNew - newDischargeNeed;// 不能带完的值

								if (dischargeCanaffort > 0) {
									newPathToDispath = newDischargeNeed;
								} else {
									newPathToDispath = maxDischrgeForNew;
								}
								for (int j = 0; j < shortestPath.size() - 1; j++) {// 最后一位为数字
									nodes[shortestPath.get(j + 1)].setDischargeTo(nodes[shortestPath.get(j)].getId(),
											newPathToDispath);// 设置流量
								}
								// 把流量加进来
								shortestPath.add(newPathToDispath);
								// 需注意，仔细检查！！！！！！！！！！！！！！现在可以将流量加上来了
								severPaths.add(shortestPath);

								newDischargeNeed -= newPathToDispath;

							} while ((dischargeCanaffort < 0) && (shortPaths.size() != 0));
							// 还是满足不了 直接安服务器 并在severPaths里面删除为了满足所做的链路
							if (dischargeCanaffort < 0) {
								for (int j = 0; j < severPaths.size(); j++) {
									List<Integer> list = severPaths.get(j);
									if (list.get(0) == pathNeedtoAdjust.get(0)) {
										severPaths.remove(j);
										// 流量还原
										for (int k = 0; k < list.size() - 2; k++) {// 最后一位为流量
											nodes[list.get(k + 1)].plusDischarge(nodes[list.get(k)].getId(),
													list.get(list.size() - 1));// 设置流量
										}
									}
								}
								nodes[pathNeedtoAdjust.get(0)].setLocatedServer(true);
								severlocation.add(nodes[pathNeedtoAdjust.get(0)].getId());

							}

						}

					}
				}

			}
			
			//现在粗略的算了一遍
			
			
			setSeverPathsResult(severPaths);

//			System.out.println("结果为");
//			for (List<Integer> list : severPaths) {
//				if (list.get(list.size() - 1) != 0) {
//					System.out.println(list.toString());
//					System.out.println(list.get(list.size() - 2));
//				}
//			}

			int price = 0;
			for (int i = 0; i < nodes.length; i++) {
				if (nodes[i].isLocatedServer()) {
					price += Const.SERVER_COST;
//					System.out.println(i + "放服务器");
				}
			}

			price += getPrice(severPaths, nodes);
//			System.out.println(price);
			return price;
		}
		

		
	}

	private int getPrice(List<List<Integer>> severPaths, NetworkNode[] nodes) {
		// TODO Auto-generated method stub
		int price = 0;
		for (List<Integer> list : severPaths) {
			for (int i = 0; i < list.size() - 2; i++) {// 最后一位是流量
				price += (nodes[list.get(i + 1)].getLinkPrice(nodes[list.get(i)].getId()))
						* (list.get(list.size() - 1));// 设置流量
			}
		}

		return price;
	}

	/**
	 * @param pathNeedtoAdjust
	 * @param nodes
	 */
	private void restoreDischarge(List<List<Integer>> subPaths, NetworkNode[] nodes) {
		// TODO Auto-generated method stub
		for (List<Integer> pathNeedtoAdjust : subPaths) {
			for (int j = 0; j < pathNeedtoAdjust.size() - 2; j++) {// 最后一位为数字
				nodes[pathNeedtoAdjust.get(j + 1)].plusDischarge(nodes[pathNeedtoAdjust.get(j)].getId(),
						pathNeedtoAdjust.get(pathNeedtoAdjust.size() - 1));// 设置流量
			}
		}

	}

	/**
	 * id是服务器节点，到id的流量设为满足要求的
	 * 
	 * @param paths
	 * @param nodes
	 * @param id
	 * @param matrix
	 */
	public void setDischarge(List<List<Integer>> severPaths, NetworkNode[] nodes, ConsumeNode[] consumeNodes,
			List<Integer> severGroup) {
		for (List<Integer> list : severPaths) {// 该服务器连接的点
			list.remove(list.size() - 1);// 最后一个是最短距离
			// 注意这儿将需要的流量加进来了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！1！！！！！！！
			int discharge = consumeNodes[nodes[list.get(0)].getComsumeNodeId()].getRequired();
			list.add(discharge);
			for (int j = 0; j < list.size() - 2; j++) {
				int require = consumeNodes[nodes[list.get(0)].getComsumeNodeId()].getRequired();
				nodes[list.get(j + 1)].setDischargeTo(nodes[list.get(j)].getId(), require);// 设置流量
				// list.add(require);
			}
		}
	}

	/**
	 * 根据起始点和终点 找到经过的左右的路线
	 * 
	 * @param fromid
	 * @param toid
	 * @param paths
	 * @return
	 */
//	private List<List<Integer>> findPathsByFromidandToid(int fromid, int toid, List<List<Integer>> paths) {
//		List<List<Integer>> subPath = new ArrayList<>();
//
//		for (int i = 0; i < paths.size(); i++) {
//			if (paths.get(i).contains(fromid) && paths.get(i).contains(toid)) {
//				if (paths.get(i).get(paths.get(i).size() - 1) == fromid
//						|| paths.get(i).get(paths.get(i).size() - 1) == toid) {
//
//				} else {
//					subPath.add(paths.get(i));
//				}
//
//			}
//		}
//
//		return subPath;
//	}

	/**
	 * 通过起始点找链路
	 * 
	 * @param consunmeid
	 * @param severPaths
	 * @return
	 */
	private List<List<Integer>> findPathsByFromid(int consunmeid, List<List<Integer>> paths) {
		// TODO Auto-generated method stub
		List<List<Integer>> subPath = new ArrayList<>();
		for (int i = 0; i < paths.size(); i++) {
			if (paths.get(i).get(0) == consunmeid) {
				subPath.add(paths.get(i));
			}
		}

		return subPath;
	}

	/**
	 * 找到这条线路里面能承受的最大值
	 * 
	 * @param path
	 * @param nodes
	 * @return
	 */
	// private int maxDischargePathCanAfford(List<Integer> path, NetworkNode[]
	// nodes) {
	// List<Integer> maxDischarge = new ArrayList<>();
	// for (int i = 0; i < path.size() - 1; i++) {// 最后一位
	// maxDischarge.add(nodes[path.get(i +
	// 1)].getMaxDischarge(nodes[path.get(i)].getId()));
	// }
	// return findMin(maxDischarge);
	//
	// }

	/**
	 * 最大的剩余流量
	 * 
	 * @param path
	 * @param nodes
	 * @return
	 */
	private int maxExtraDischargePathCanAfford(List<Integer> path, NetworkNode[] nodes) {
		List<Integer> maxDischarge = new ArrayList<>();
		for (int i = 0; i < path.size() - 1; i++) {// 最后一位已经去除
			maxDischarge.add(nodes[path.get(i + 1)].getExtraDischarge(nodes[path.get(i)].getId()));
		}
		if (findMin(maxDischarge) > 0) {
			return findMin(maxDischarge);
		} else {
			return 0;
		}

	}

	/**
	 * 找到最小值
	 * 
	 * @param max
	 * @return
	 */
	private int findMin(List<Integer> max) {
		int min = 1000000;
		for (int i : max) {
			if (i < min) {
				min = i;
			}
		}
		return min;
	}

	/**
	 * 将一个数组 从小到大排列获取之前的位置
	 * 
	 * @param node
	 * @return
	 */
	private List<Integer> findPosition(List<Integer> array) {
		// map的key存放数组中存在的数字，value存放该数字在数组中出现的次数
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		List<Integer> order = new ArrayList<>();

		for (int i = 0; i < array.size(); i++) {
			map.put(i, array.get(i));
		}

		array.sort(null);

		for (int i = 0; i < array.size(); i++) {
			for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
				// 得到value为maxCount的key，也就是数组中出现次数最多的数字
				if (array.get(i) == entry.getValue()) {
					order.add(entry.getKey());
					map.remove(entry.getKey());
					break;
				}
			}

		}

		return order;
	}
	
	
	/**输出结果
	 * @param severPath
	 * @param nodes
	 * @return
	 */
	public String[] resultOutPut(List<List<Integer>> severPath,NetworkNode[]nodes,ConsumeNode[] consumeNodes) {
//		String[] outPut=null;
		List<String> finaPaths=new ArrayList<>();
		int pathNumber=0;
		for (int i=0;i<severPath.size();i++) {
			List<Integer> path=severPath.get(i);
			if (path.get(path.size()-1)!=0) {				
				pathNumber++;
			}
		}
		for (ConsumeNode consumeNode : consumeNodes) {
			if(nodes[consumeNode.getNetworkNodeId()].isLocatedServer()){
				pathNumber++;
			}
		}
		finaPaths.add(Integer.toString(pathNumber));
//		pathsFinal.add(pathNumber);
//		finaPaths.add("\n");
		for (int i=0;i<severPath.size();i++) {
			List<Integer> path=severPath.get(i);
			List<Integer> pathFinal=new ArrayList<>();
			if (path.get(path.size()-1)!=0) {
				for (int j = path.size()-2; j >=0; j--) {
					pathFinal.add(path.get(j));			
				}
				int consumeid=getConsunmeId(consumeNodes,path.get(0));
				pathFinal.add(consumeid);
				pathFinal.add(path.get(path.size()-1));
				finaPaths.add(listToString(pathFinal));
//				pathsFinal.add(pathFinal);			
			}
		}
		//如果是服务器放在消费点直接相连的地方
		for (int i = 0; i < consumeNodes.length; i++) {
			
			if (nodes[consumeNodes[i].getNetworkNodeId()].isLocatedServer()) {	
				List<Integer> path=new ArrayList<>();
				path.add(consumeNodes[i].getNetworkNodeId());
				path.add(consumeNodes[i].getId());
				path.add(consumeNodes[i].getRequired());
				finaPaths.add(listToString(path));
//				pathsFinal.add(path);
			}
			
		}
		
		
		return geshi(finaPaths);
	}
	
	//将int列表转成字符串2 3 4形式
	private String listToString(List<Integer> list){
		
		StringBuilder sb=new StringBuilder();
		int N=list.size();
		for(int i=0;i<N;i++){
			if(i==N-1){
				sb.append(list.get(i));
			}else{
				sb.append(list.get(i)+" ");
			}
		}
		return sb.toString();
		
	}
	
	private String[] geshi(List<String> list) {
		    int N = list.size();
	        String[] result = new String[N+1];
	        result[0] = list.get(0);
	        result[1] = "";

	        StringBuilder sb = null;
	        for (int i = 1; i < N; i++) {

	        	/*String string=list.get(i);
	            sb = new StringBuilder(string);	            	            
	            sb.deleteCharAt(0).deleteCharAt(sb.length() - 1);
	            	            
	            for (int j = 0; j < sb.length(); j++) {
					if(sb.indexOf(",")==j){
						sb.deleteCharAt(j);
					}
				}*/
	            result[i+1] = list.get(i);

	        }
	        return result;
		
	}
	

	/**根据最后的点 获取与消费点直连的点
	 * @param consumeNodes
	 * @param integer
	 * @return
	 */
	private int getConsunmeId(ConsumeNode[] consumeNodes, Integer integer) {
		// TODO Auto-generated method stub
		int id=0;
		for (ConsumeNode consumeNode : consumeNodes) {
			if(consumeNode.getNetworkNodeId()==integer){
				id=consumeNode.getId();
				break;
			}
		}
		return id;
	}

	public List<List<Integer>> getSeverPathsResult() {
		return severPathsResult;
	}

	public void setSeverPathsResult(List<List<Integer>> severPathsResult) {
		this.severPathsResult = severPathsResult;
	}

	

}
